package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.List;

import zcw.com.lib_leet_code.bean.ListNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/8/24.<br><br>
 *
 * 简单：相交链表
 */
public class Topic160 {

    public static void main(String[] args) {
        Topic160 instance = new Topic160();

        int[] arrayA = new int[] {4,1};
        int[] arrayB = new int[] {5,6,1};
        ListNode common = Util.createList(new int[] {8,4,5});
        ListNode headA = Util.listAdd(Util.createList(arrayA), common);
        ListNode headB = Util.listAdd(Util.createList(arrayB), common);
        Util.printList(instance.getIntersectionNode(headA, headB));

        arrayA = new int[] {1,9,1};
        arrayB = new int[] {3};
        common = Util.createList(new int[] {2,4});
        headA = Util.listAdd(Util.createList(arrayA), common);
        headB = Util.listAdd(Util.createList(arrayB), common);
        Util.printList(instance.getIntersectionNode(headA, headB));

        arrayA = new int[] {2,6,4};
        arrayB = new int[] {1,5};
        headA = Util.createList(arrayA);
        headB = Util.createList(arrayB);
        Util.printList(instance.getIntersectionNode(headA, headB));
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) {
            return null;
        }

        ListNode nodeA = headA;
        ListNode nodeB = headB;

        while (nodeA != nodeB) {
            nodeA = nodeA == null ? headB : nodeA.next;
            nodeB = nodeB == null ? headA : nodeB.next;
        }

        return nodeA;
    }

    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        List<ListNode> list = new ArrayList<>();

        while (headA != null && headB != null) {
            if(list.contains(headA)) {
                return headA;
            }

            list.add(headA);
            headA = headA.next;

            if(list.contains(headB)) {
                return headB;
            }

            list.add(headB);
            headB = headB.next;
        }

        while (headA != null) {
            if(list.contains(headA)) {
                return headA;
            }

            list.add(headA);
            headA = headA.next;
        }

        while (headB != null) {
            if(list.contains(headB)) {
                return headB;
            }

            list.add(headB);
            headB = headB.next;
        }

        return null;
    }
}
